package 数据结构.链表;

import java.util.*;

class JZ24反转链表 {
    public static ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ArrayList arrayList = new ArrayList();
        while (head != null) {
            arrayList.add(head);
            head = head.next;
        }
        Collections.reverse(arrayList);
        ListNode newHead = (ListNode) arrayList.get(0);
        ListNode p = newHead;
        for (int i = 1; i < arrayList.size(); i++) {
            p.next = (ListNode) arrayList.get(i);
            p = p.next;
        }
        //解除环
        p.next = null;
        return newHead;
    }


    public static ListNode ReverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newhead = null;
        while (head != null) {
            ListNode temp =head.next;

            head.next = newhead;

            newhead = head;

            head = temp;
        }
        return newhead;
    }
    

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode head = listNode;
        listNode.next = new ListNode(2);
        listNode = listNode.next;
        listNode.next = new ListNode(3);
        ListNode listNode1 = ReverseList(head);
        System.out.println(listNode1);
    }
}
